A = 26
def query1(x):
print("?", 1, x + 1, flush=True)
return ord(input()) - ord('a')
def query2(l, r):
print("?", 2, l + 1, r + 1, flush=True)
return int(input())
n = int(input())
last_appearance = [-1] * A
discovered_letters = 0
answer = [0] * n
for i in range(n):
if query2(0, i) > discovered_letters:
discovered_letters += 1
answer[i] = query1(i)
last_appearance[answer[i]] = i
else:
my_list = []
for j in range(A):
if last_appearance[j] != -1:
my_list.append((last_appearance[j], j))
my_list.sort()
l, r = 0, len(my_list) - 1
while l <= r:
mid = (l + r) // 2
if query2(my_list[mid][0], i) == len(my_list) - mid + 1:
r = mid - 1
else:
l = mid + 1
answer[i] = my_list[l - 1][1]
last_appearance[answer[i]] = i
print("!", end = " ", flush = True)
[print(chr(x + ord('a')), end = "", flush=True) for x in answer]
print("", flush=True)
#include<bits/stdc++.h>
#include<math.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ll long long int
#define fr(i, a, n) for(ll i=a; i<n; i++)
#define frn(i, a, n) for(ll i=a; i>n; i--)
#define pll pair<ll, ll>
#define vll vector<ll>
#define append push_back
#define add insert
#define umap unordered_map
#define pqu priority_queue
using namespace std;
using namespace __gnu_pbds;
// typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
//order_of_key (k) : Number of items strictly smaller than k .
//find_by_order(k) : pointer to K-th element in a set (counting from zero).
// custom set comparator set<vector<int>, decltype(cmp)*> s1(cmp);
const ll maxi = 200005, mod = 1000000007, inf = 1e16;
ll testcc, n, k, ans;
void qur1(ll a) {
cout << "? " << 1 << " " << a << endl;
}
void qur2(ll a, ll b) {
cout << "? " << 2 << " " << a << " " << b << endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#ifndef ONLINE_JUDGE
// for getting input from input.txt
freopen("input.txt", "r", stdin);
// for writing output to output.txt
freopen("output.txt", "w", stdout);
#endif
cin >> n;
vector<char> str1(n, ' ');
map<char, ll> m1;
qur1(1);
cin >> str1[0];
m1[str1[0]] = 0;
ll t = 1;
fr(i, 2, n + 1) {
qur2(1, i);
ll p; cin >> p;
if (p == t) {
// perform the binary search
vector<ll> temp(m1.size(), 0);
ll cind = 0;
for (auto ele : m1) {
temp[cind] = ele.second;
cind += 1;
}
sort(temp.begin(), temp.end());
ll l = 0, r = temp.size() - 1, m, sz = temp.size(), tempans = 0;
while (l <= r) {
m = (l + r) / 2;
qur2(temp[m] + 1, i);
ll k; cin >> k;
if (k == sz - m) {
tempans = m;
l = m + 1;
}
else {
r = m - 1;
}
}
str1[i - 1] = str1[temp[tempans]];
}
else {
qur1(i);
cin >> str1[i - 1];
m1[str1[i - 1]] = 0;
}
t = p;
m1[str1[i - 1]] = i - 1;
}
cout << "! ";
fr(i, 0, n) {
cout << str1[i];
}
cout << endl;
return 0;
}470. Implement Rand10() Using Rand7() | 866. Prime Palindrome |
1516A - Tit for Tat | 622. Design Circular Queue |
814. Binary Tree Pruning | 791. Custom Sort String |
787. Cheapest Flights Within K Stops | 779. K-th Symbol in Grammar |
701. Insert into a Binary Search Tree | 429. N-ary Tree Level Order Traversal |
739. Daily Temperatures | 647. Palindromic Substrings |
583. Delete Operation for Two Strings | 518. Coin Change 2 |
516. Longest Palindromic Subsequence | 468. Validate IP Address |
450. Delete Node in a BST | 445. Add Two Numbers II |
442. Find All Duplicates in an Array | 437. Path Sum III |
436. Find Right Interval | 435. Non-overlapping Intervals |
406. Queue Reconstruction by Height | 380. Insert Delete GetRandom O(1) |
332. Reconstruct Itinerary | 368. Largest Divisible Subset |
377. Combination Sum IV | 322. Coin Change |
307. Range Sum Query - Mutable | 287. Find the Duplicate Number |